ABC002 D - 派閥
https://atcoder.jp/contests/abc002/tasks/abc002_4
提出
code: python
n, m = map(int, input().split())
xy = list(map(int, input().split())) for _ in range(m)
class UnionFind:
def __init__(self, n):
# 親要素のノード番号を格納。parx == xの時そのノードは根(最初は全て根)
self.par = i for i in range(n)
# 木の高さを格納する（初期状態では0）
self.rank = 0 * n
# 人間の数
self.size = 1 * n
# 検索
def find(self, x):
# 根ならその番号を返す
if self.parx == x:
return x
# 根でないなら、親の要素で再検索
else:
# 走査していく過程で親を書き換える(return xが代入される)
self.parx = self.find(self.parx)
return self.parx
# 併合
def union(self, x, y):
# 根を探す
x = self.find(x)
y = self.find(y)
if x == y:
return
# 木の高さを比較し、低いほうから高いほうに辺を張る
if self.rankx < self.ranky:
self.parx = y
self.sizey += self.sizex
else:
self.pary = x
self.sizex += self.sizey
# 木の高さが同じなら片方を1増やす
if self.rankx == self.ranky:
self.rankx += 1
# 同じ集合に属するか判定
def same(self, x, y):
return self.find(x) == self.find(y)
UF = UnionFind(n)
for i in xy:
UF.union(i0, i1)
ans = [UF.sizeUF.find(iam) - 1 for iam in range(n)]
print(ans)
解答
code: python
from itertools import combinations
from collections import defaultdict
n, m = map(int, input().split())
xy = list(map(int, input().split())) for _ in range(m)
d = defaultdict(list)
for x, y in xy:
dx-1.append(y-1)
dy-1.append(x-1)
# {1: 2, 3, 2: 1, 3, 3: 2, 1}
# 最大の派閥に属する議員数を求めたいので、議員数が多くなるような集合から先に考える
for i in range(n, 1, -1): # N, N-1, N-2, ... 2
for member in combinations(range(n), i):
flag = True
for pair in combinations(member, 2): # 議員の集合に対して考えられるペアを列挙
if (pair0 not in d[pair1]) or (pair1 not in d[pair0]):
flag = False # 一つでも知り合いでない組があればNG
break
if flag: # 派閥が作れた段階でプログラムを終了
print(i)
exit()
print(1)
テーマ
蟻本 2-1 部分和問題
メモ
ABC002D 派閥
提出
code: python
from collections import defaultdict
n, m = map(int, input().split())
xy = list(map(int, input().split())) for _ in range(m)
d = defaultdict(list)
for x, y in xy:
dx.append(y)
dy.append(x)
print(d)